package hyy_2022;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 1、  0,1,···,n-1这n个数字排成一个圆圈，从数字0开始
 * 2、  每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）
 * 3、  求出这个圆圈里剩下的最后一个数字
 */
public class _0806_Offer62_LastRemaining {
    public static void main(String[] args) {
        lastRemaining(5,3);
    }


    /**
     * 胡瑶瑶解法, 采用队列的方法好像行不通, 会超出时间限制
     * @param n
     * @param m
     * @return int
     */
    public static int lastRemaining(int n, int m) {
        Queue<Integer> q = new LinkedList<>();
        //入队
        for(int i=0;i<n;i++) {
            q.offer(i);
        }
        //从圈圈删除第m个元素, 相当于把队列中m-1个元素出队,然后再入队,删除队列第m个元素
        //然后从m个元素之后继续上一步操作
        int k = 0;
        while(q.size() != 1) {
            k ++;
            if(k == m) {
                q.poll();
                k = 0;
            } else {
                q.offer(q.poll());
            }
        }
        return  q.peek();
    }

    public static int lastRemaining1(int n, int m) {
        ArrayList<Integer> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int idx = 0;
        while (n > 1) {
            idx = (idx + m - 1) % n;
            list.remove(idx);
            n--;
        }
        return list.get(0);
    }
}
